public class Leetcode {
}

//leetcode:1137:第N个泰波那契数
//动态规划
class Solution1 {
    public int tribonacci(int n) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = dp[2] = 1;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }
}
//动态规划:空间优化:滚动数组
class Solution2 {
    public int tribonacci(int n) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
        int a = 0, b = 0, c = 1, d = 1;
        for(int i = 3; i <= n; i++){
            a = b;
            b = c;
            c = d;
            d = a + b + c;
        }
        return d;
    }
}

//leetcode:面试题 08.01.三步问题
//动态规划
class Solution3 {
    public int waysToStep(int n) {
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;

        int MOD = (int) 1e9 + 7;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for(int i = 4; i <= n;i++){
            dp[i] = ((dp[i-1] + dp[i-2])% MOD + dp[i-3])% MOD;
        }
        return dp[n];
    }
}

//动态规划:空间优化:滚动数组
class Solution4 {
    public int waysToStep(int n) {
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;

        int MOD = (int) 1e9 + 7;
        int[] dp = new int[n+1];
        int a = 1, b = 2, c = 4 ,d = 0;
        for(int i = 4; i <= n;i++){
            d = ((a + b) % MOD + c) % MOD;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
}